今天的題單：

• Diameter of Binary Tree

• Middle of the Linked List

543. Diameter of Binary Tree

思路：tree 裡最長的 path 一定是 leaf 到 leaf（在左右 subtree 都有的情況下），所以需要 node 左右子樹的深度，並計算左右子樹的深度加總。

對於每一個 node

• 計算左子樹和右子樹的深度 （node.left_depth, node.right_depth）

• 記錄當前最大的 diameter：max (diameter, node.left_depth + node.right_depth)

• 回傳以 node 為 root 的 tree 深度：max (node.left_depth + node.right_depth)

要 bottom up 計算，使用 dfs 實作。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0;
        
        depth(root, diameter);
        
        return diameter;
    }

    int depth(TreeNode* node, int& diameter) {
        // empty node
        if (node == nullptr) {
            return -1;
        }
        // leaf
        if (node->left == nullptr && node->right == nullptr) {
            return 0;
        }

        // calculate the left and right subtree depth
        // plus one to add the edge to this node
        int left_depth = depth(node->left, diameter) + 1;
        int right_depth = depth(node->right, diameter) + 1;

        diameter = max(diameter, left_depth + right_depth);

        return max(left_depth, right_depth);
    }
};

876. Middle of the Linked List

思路：先 scan 一遍看 list 長度是多少，就知道 middle node 的位置。

First attempt 是把 node address 全部記起來，scan 完後直接取中間點。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        vector<ListNode*> address(105);
        int count = 0;

        ListNode* ptr = head;

        while (ptr != nullptr) {
            address[count] = ptr;
            ptr = ptr->next;
            count++;
        }

        count = count / 2;
        
        return address[count];
    }
};

把後半改成用 pointer 爬到中間 node，有比較快（有點謎，是 vector 存取較慢嗎）。
優化後是O(n) time 和 O(1) space。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        int length = 0;

        ListNode* ptr = head;

        while (ptr != nullptr) {
            ptr = ptr->next;
            length++;
        }

        ptr = head;
        for (int i = 0; i < length / 2; i++) {
            ptr = ptr->next;
        }
        return ptr;
    }
};

另外一種思路：two-pointer approach，fast pointer 走快兩倍，走完後 slow pointer 剛好到 middle node。一樣是 O(n) time 和 O(1) space。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* ptr1 = head;
        ListNode* ptr2 = head;

        while (ptr2 != nullptr) {
            if (ptr2->next == nullptr)
                break;
            ptr2 = ptr2->next->next;
            ptr1 = ptr1->next;
        }
        return ptr1;
    }
};